Asynchronous transfer mode (ATM) is rapidly becoming the technology of choice for high speed broad-band communications. The fixed length data element or cell permits the transport of multimedia data including voice and video from a network source to a network destination. The ATM Forum has defined five categories of service for ATM cell traffic including both real time and non-real time connections. The five categories of service are: constant bit rate (CBR); real time variable bit rate (rtVBR); non-real time variable bit rate (nrtVBR); available bit rate (ABR); and unspecified bit rate (UBR). The quality of service (QoS) for each service category has also been specified in order to accommodate the different traffic requirements. Obviously real time traffic cannot tolerate significant time delays through the network. On the other hand, data traffic such as electronic-mail can tolerate time delays but must ensure minimal cell loss.
Available bit rate (ABR) service category is one of the most important mechanisms for carrying bandwidth on demand traffic such as today's local area network (LAN) traffic. ABR traffic is particularly significant in that it makes optimum use of network bandwidth by dynamically adjusting its transmission rate to use the bandwidth not involved in higher priority traffic. In order to make optimum use of the bandwidth and still ensure minimal cell loss the ABR service category employs a feedback loop which monitors network congestion and returns congestion information to the data source. The congestion information is carried in resource management (RM) cells within the cell header. The resource management cells receive congestion information at each node as the ABR traffic progresses from the source to the destination. At the destination the resource management cell is returned to the source, again passing through each node where updated congestion information may be inserted. The congestion information may indicate that the source traffic should continue at its present rate or that it should be reduced in view of severe congestion. A third type of information that may be carried by the resource management cell is explicit rate (ER) information. Explicit rate information is an indication of the ABR traffic which may be transmitted from the source without increasing congestion to the point where cells may be dropped.
Explicit rate information is based on the instantaneous bandwidth available to ABR traffic, i.e. bandwidth not committed to CBR and VBR traffic, and the number of connections or contention points requiring bandwidth. It is understood that explicit rate marking provides a better network utilization performance by forcing the ABR source to transmit at a desirable rate during network congestion conditions. Not only does ER marking encourage faster rate convergence under congestion, but it provides better fairness to ABR connections competing for the same network resources, both bandwidth and buffer usage.
Many explicit rate algorithms have been identified and most of these have a common characteristic in that division is involved. The division arithmetic is employed in these algorithms to distribute bandwidth fairly amongst the competing ABR connections. To realize such an operation poses a serious challenge especially at today's ATM interface speed which operates at hundreds of megabits per second. Division is viewed as an infrequent operation by the computing design community because of the significantly greater number of processing steps than are required for addition, subtraction and multiplication. The larger number of processing steps result in greater time delays and/or system complexity.
To handle ABR flow control at an ATM interface, the ER algorithm must operate in real time to sustain the required throughput. Regrettably, it does not enjoy the luxury of using a low-latency divider as in the environment of a general purpose computer. The present invention addresses this dilemma by bypassing the division operation in quotient-based explicit rate algorithms thus achieving a high throughput without incurring the high cost and design complexity of a high speed floating point divider.